﻿#define _CRT_SECURE_NO_WARNINGS 1
//合并K个升序链表(hard):https://leetcode.cn/problems/merge-k-sorted-lists/
class Solution
{
	struct cmp
	{
		bool operator()(const ListNode* l1, const ListNode* l2)
		{
			return l1->val > l2->val;
		}
	};
public:
	ListNode* mergeKLists(vector<ListNode*>& lists)
	{
		// 创建⼀个⼩根堆
		priority_queue<ListNode*, vector<ListNode*>, cmp> heap;
		// 让所有的头结点进⼊⼩根堆
		for (auto l : lists)
			if (l) heap.push(l);
		// 合并 k 个有序链表
		ListNode* ret = new ListNode(0);
		ListNode* prev = ret;
		while (!heap.empty())
		{
			ListNode* t = heap.top();
			heap.pop();
			prev->next = t;
			prev = t;
			if (t->next) heap.push(t->next);
		}
		prev = ret->next;
		delete ret;
		return prev;
	}
};